public class MyLinkedList {
    static class ListNode{
        public int val;
        public ListNode prev;
        public ListNode next;
        public ListNode head;
        public ListNode last;
        public ListNode(int val){
            this.val=val;
        }

        //头插法
        public void addFirst(int data){
            ListNode node=new ListNode(data);
            if(head==null){
                head=node;
                last=node;
                return;
            }
            node.next=head;
            head.prev=node;
            head=node;
        }
        //尾插法
        public void addLast(int data){
            ListNode node=new ListNode(data);
            if(head==null){
                head=node;
                last=node;
                return;
            }
            last.next=node;
            node.prev=last;
            last=node;
        }
        //任意位置插入
        public boolean addIndex(int index,int data){
            if(index<0||index>size())return false;
            ListNode cur=findInIndex(index-1);
            ListNode node=new ListNode(data);
            cur.next.prev=node;
            node.next=cur.next;
            cur.next=node;
            node.prev=cur;
            return true;
        }
        //查找是否包含key
        public boolean contains(int key){
            ListNode cur=head;
            while(cur!=null){
                if(cur.val==key)return true;
            }
            return false;
        }
        //删除第一次出现为Key的节点
        public void remove(int key){
            ListNode cur = head;
            while (cur != null) {
                if (cur.val == key) {
                    if (cur == head) {
                        head = head.next;
                        if(head!=null){
                            head.prev=null;
                        }
                    }
                    else {
                        cur.prev.next = cur.next;
                        if(cur.next!=null) {
                            cur.next.prev = cur.prev;
                        }else{
                            last=cur.prev;
                        }
                    }
                    break;
                }
            }
        }
        //删除所有为key的节点
        public void removeAllkey(int key) {
            ListNode cur = head;
            while (cur != null) {
                if (cur.val == key) {
                    if (cur == head) {
                        head = head.next;
                        if(head!=null){
                            head.prev=null;
                        }
                    }
                    else {
                        cur.prev.next = cur.next;
                        if(cur.next!=null) {
                            cur.next.prev = cur.prev;
                        }else{
                            last=cur.prev;
                        }
                    }
                }
                cur=cur.next;
            }
        }
        public int size(){
            int count=0;
            ListNode cur=head;
            while(cur!=null){
                count++;
                cur=cur.next;
            }
            return count;
        }
        public void display(){
            ListNode cur=head;
            while(cur!=null){
                System.out.print(cur.val+" ");
                cur=cur.next;
            }
            System.out.println();
        }
        public void clear(){
            head=null;
            last=null;
        }
        public ListNode findInIndex(int index){
            int count=0;
            ListNode cur=head;
            while(cur!=null){
                cur=cur.next;
                count++;
                if(count==index){
                    break;
                }
            }
            return cur;
        }
    }
}
